package io.github.consoles.dsa;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by yiihua-013 on 17/6/11.
 * <p>
 * 约瑟夫环
 */
public class Josephus {

    /**
     * 自然模拟
     *
     * @param m
     * @param n
     * @return
     */
    public int mock(int m, int n) {
        List<Integer> data = new ArrayList<>();
        for (int i = 0; i < m; i++) data.add(i);

        List<Integer> deleteList = new ArrayList<>();

        int start = 0; // 从0开始报数
        while (true) {
            int toDeleteIndex = start + n - 1;
            if (toDeleteIndex > data.size() - 1) {
                toDeleteIndex %= data.size();
            }
            deleteList.add(data.get(toDeleteIndex));
            data.remove(toDeleteIndex);
            start = toDeleteIndex;
            if (data.size() == 1) {
                int ret = data.get(0);
                deleteList.add(ret);
                data.remove(toDeleteIndex);
                System.out.println(deleteList);
                return ret;
            }
        }
    }

    /**
     * http://www.acmerblog.com/joseph-problem-3394.html
     * https://www.zhihu.com/question/20065611
     *
     * @param m
     * @param n
     * @return
     */
    public int recursion(int m, int n) {
        int s = 0;
        for (int i = 2; i <= n; i++) {
            s = (s + m) % i;
        }
        return s + 1;
    }

    public void byQueue(int m, int n) {
        LinkedQueue<Integer> q = new LinkedQueue<>();
        for (int i = 0; i < m; i++) q.enqueue(i);

        int k = 0;
        while (!q.isEmpty()) {
            int x = q.dequeue();

            if (++k % n == 0) System.out.println(x);
            else q.enqueue(x);
        }
    }

    public void byQueue2(int m, int n) {
        LinkedQueue<Integer> q = new LinkedQueue<>();
        for (int i = 0; i < m; i++) q.enqueue(i);

        // 报数的人将会出列,并得到自己的号,如果与M相等则出列.并重置报数
        // 反之,不断地入列直到有人出局
        int start = 1;
        while (!q.isEmpty()) {
            int item = q.dequeue();
            if (start == n) {
                System.out.println(item);
                start = 1;
            } else {
                q.enqueue(item);
                start++;
            }
        }
    }
}
